package kmp;

import java.util.ArrayList;

public class SubtreeOfAnotherTree {


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }


    public static boolean isSubtree(TreeNode t1, TreeNode t2) {
        if (t1 != null && t2 != null) {
            return same(t1, t2) || isSubtree(t1.left, t2) || isSubtree(t1.right, t2);
        }

        return t2 == null;
    }

    /**
     * 判断两颗树是否一样
     *
     * @param t1 树根节点
     * @param t2 树根节点
     * @return 是否一样
     */
    private static boolean same(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return true;
        }

        if (t1 != null && t2 != null) {
            return t1.val == t2.val && same(t1.left, t2.left) && same(t1.right, t2.right);
        }

        return false;
    }

    public static boolean isSubtree2(TreeNode t1, TreeNode t2) {
        if (t1 != null && t2 != null) {
            ArrayList<String> s1 = new ArrayList<>();
            ArrayList<String> s2 = new ArrayList<>();

            serial(t1, s1);
            serial(t2, s2);

            return kmp(s1, s2) != -1;
        }

        return t2 == null;
    }

    private static int kmp(ArrayList<String> s1, ArrayList<String> s2) {
        int n = s1.size(), m = s2.size(), x = 0, y = 0;
        int[] next = nextArray(s2, m);

        while (x < n && y < m) {
            if (isEqual(s1.get(x), s2.get(y))) {
                x++;
                y++;
            } else if (y == 0) {
                x++;
            } else {
                y = next[y];
            }
        }
        // 匹配到子树？ 计算根节点下标: -1
        return y == m ? x - y : -1;
    }

    private static boolean isEqual(String a, String b) {
        if (a == null && b == null) {
            return true;
        }
        if (a != null && b != null) {
            return a.equals(b);
        }
        return false;
    }

    private static int[] nextArray(ArrayList<String> tree, int m) {
        if (m == 1) {
            return new int[]{-1};
        }
        int[] next = new int[m];
        next[0] = -1;
        next[1] = 0;

        int i = 2, cn = 0;

        while (i < m) {
            if (isEqual(tree.get(i - 1), tree.get(cn))) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }

        return next;
    }

    /**
     * 前序遍历二叉树，并序列化
     *
     * @param head 头节点
     * @param path 序列号的结果
     */
    private static void serial(TreeNode head, ArrayList<String> path) {
        if (head == null) {
            path.add(null);
        } else {
            // 根
            path.add(String.valueOf(head.val));
            // 左
            serial(head.left, path);
            // 右边
            serial(head.right, path);
        }
    }
}
